Extending classical algorithms for ordinary weighted or string-to-string automata to automata with underlying more general algebraic structures is of significant practical and theoretical interest. However, the generalization ...